'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-09 21:15:39
'''
'''
148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

写了一半快排，可是快排不是所有情况都可以O(nlogn)，不过挺有意思，调了半天，记录在这。正确做法应该是归并。
'''

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def sortList1(self, head: ListNode) -> ListNode:
        def recurse(head, std, cnt):
            if not head:
                return
            if cnt<=1:
                return
            t=0
            pre = head
            move = head
            pre_cnt = 0
            pre_std = 0
            move_std = 0
            while t<cnt-1:
                if move.val<std:
                    pre.val, move.val = move.val, pre.val
                    pre_std = pre.val
                    pre = pre.next
                    move = move.next
                    move_std = move.val
                    pre_cnt+=1
                else:
                    move=move.next
                    move_std = move.val
                t+=1
            # print(t, cnt, std)
            # tmp = head
            # re = ''
            # while tmp:
            #     re += ',' + str(tmp.val)
            #     tmp=tmp.next
            # print(re)
            move.val, pre.val = pre.val, move.val
            # tmp = head
            # re = ''
            # while tmp:
            #     re += ',' + str(tmp.val)
            #     tmp=tmp.next
            # print(re)
            recurse(head, pre_std, pre_cnt)
            recurse(pre.next, move.val, cnt-pre_cnt-1)
        cnt = 0
        cnt_head = head
        std = 0
        while cnt_head:
            cnt+=1
            std = cnt_head.val
            cnt_head=cnt_head.next
        recurse(head, std, cnt)
        return head

    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head # termination.
        # cut the LinkedList at the mid index.
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None # save and cut.
        # recursive for cutting.
        left, right = self.sortList(head), self.sortList(mid)
        # merge `left` and `right` linked list and return it.
        h = res = ListNode(0)
        while left and right:
            if left.val < right.val: h.next, left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next

if __name__ == "__main__":
    lis = [4,2,1,3]
    head = ListNode(lis[0])
    pre = head
    for l in lis[1:]:
        tmp = ListNode(l)
        pre.next = tmp
        pre = pre.next
    solution = Solution()
    re = []
    head = solution.sortList1(head)
    while head:
        re.append(head.val)
        head = head.next
    print(re)